#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 常量定义：N为数组大小，D为阈值（约等于sqrt(1e9)）
const int N = 1e5 + 5, D = sqrt(1e9);
int T, n, m, MOD, A, B, X;

/**
 * 快速幂算法
 * @param a 底数
 * @param x 指数
 * @return a^x mod MOD
 */
ll qpow(ll a, ll x) {
  ll z = 1;
  for (; x; x >>= 1, a = a * a % MOD)
    if (x & 1)
      z = z * a % MOD;
  return z;
}

typedef pair<ll, ll> pii; // 定义pair类型，first存储和，second存储幂

/**
 * 分治法计算等比数列和：∑(i=0 to x-1) a^i
 * 使用分治策略避免除法（因为模运算中除法需要求逆元）
 * @param a 等比数列的公比
 * @param x 项数
 * @return pair<等比数列和, a^x>
 */
pii work(ll a, ll x) {
  // 基本情况：只有1项
  if (x == 1)
    return pii(1, a);

  // 递归计算前半部分
  pii res = work(a, x / 2);
  
  ll ret = res.first, pw = res.second;

  // 如果x是奇数：S = S_half * (1 + a^(x/2)) * a + 1
  if (x & 1)
    return pii(((ret + ret * pw) % MOD * a % MOD + 1) % MOD,
               pw * pw % MOD * a % MOD);
  // 如果x是偶数：S = S_half * (1 + a^(x/2))
  else
    return pii((ret + ret * pw) % MOD, pw * pw % MOD);
}

/**
 * 计算等比数列 X^(d0) + X^(d0+d1) + ... + X^(d0+(len-1)*d1)
 * 即：X^d0 * ∑(i=0 to len-1) X^(i*d1)
 * @param d0 起始指数
 * @param d1 公差（步长）
 * @param len 项数
 * @return 等比数列和 mod MOD
 */
ll solve(int d0, int d1, int len) {
  // 如果d1为负数，转换为正数处理（利用对称性）
  if (d1 < 0)
    return solve(d0 + 1ll * (len - 1) * d1, -d1, len);
  // 计算：X^d0 * (1 + X^d1 + X^(2*d1) + ... + X^((len-1)*d1))
  return qpow(X, d0) * work(qpow(X, d1), len).first % MOD;
}

int main() {
  freopen("g.in", "r", stdin);
  freopen("g.out", "w", stdout);
  cin >> T;
  while (T--) {
    // 输入：n项数, m模数, A/B线性参数, X底数, MOD结果模数
    cin >> n >> m >> A >> B >> X >> MOD;
    ll ans = 0;

    // 情况1：n较小，直接暴力计算
    if (n <= D) {
      for (int i = 0; i < n; ++i)
        // 计算每项：X^((A*i+B) mod m) 并累加
        (ans += qpow(X, (1ll * A * i + B) % m)) %= MOD;
      cout << ans << endl;
    }
    // 情况2：n较大，使用优化算法
    else {
      int d, h; // d: 分组大小, h: 组内步长

      // 寻找合适的d，使得A*d mod m的值很小（正小或负小）
      // 这样在模m意义下，连续的d项会形成近似等差序列
      for (int i = 1;; i++) {
        // 如果A*i mod m 是正小值
        if (1ll * A * i % m <= m / D) {
          d = i, h = 1ll * A * i % m;
          break;
        }
        // 如果A*i mod m 是负小值（接近m）
        if (1ll * A * i % m >= m - m / D) {
          d = i, h = -(m - 1ll * A * i % m); // 转换为负数
          break;
        }
      }

      int cnt = 0; // 计数器（调试用）

      // 将序列分成d组（模d同余的项为一组）
      for (int i = 0; i < d; ++i) {
        // 处理第i组：起始位置为i，步长为d
        for (int j = i; j < n;) {
          // 当前项的指数值
          int v0 = (1ll * A * j + B) % m, step;

          // 计算当前连续段的长度（step）
          if (h >= 0) {
            if (h != 0)
              // 计算从v0开始，步长为h，不超过m的连续项数
              step = (m - v0 + h - 1) / h;
            else
              // h=0时，所有项指数相同，直接计算剩余项数
              step = (n - j + d - 1) / d;
          } else {
            // h为负数时，计算从v0开始递减的连续项数
            step = v0 / (-h) + 1;
          }

          // 确保step不会超出n的范围
          if (j + 1ll * step * d >= n) {
            step = (n - j + d - 1) / d;
            assert(j + (step - 1) * d < n); // 调试断言
          }

          ++cnt;
          // 计算当前连续段的等比数列和并累加到答案
          (ans += solve(v0, h, step)) %= MOD;
          // 移动到下一段
          j += step * d;
        }
      }

      // 输出结果（确保非负）
      cout << (ans + MOD) % MOD << endl;
    }
  }
  return 0;
}